Convex Optimization: Approximating Inequalities: From Indicator Functions to Smooth Barriers

Imagine you are piloting a high-frequency trading algorithm. Your portfolio has a strict risk limit. A "hard" constraint acts like an emergency brake—it stops everything abruptly the moment the limit is touched, potentially crashing the system's logic. In convex optimization, we prefer a "soft" warning system. We replace the jagged, binary cliff of the indicator function with a smooth, logarithmic "barrier" that penalizes the objective more and more as we drift toward the boundary. This allows the optimizer to "feel" the constraint coming and adjust its trajectory smoothly without ever stepping out of bounds.

The Problem of Non-Differentiability

The standard constrained optimization problem is defined as:

$$\text{minimize } f_0(x) \\ \text{subject to } f_i(x) \leq 0, \quad i = 1, \ldots, m \\ Ax = b$$

We could theoretically rewrite this using the indicator function $I_-(u)$ to absorb constraints into the objective. However, $I_-(u)$ is a monster for calculus:

$$I_-(u) = \begin{cases} 0 & u \leq 0 \\ \infty & u > 0 \end{cases}$$

Because it is discontinuous and has an infinite gradient at the boundary, we cannot compute the Hessian required for Newton's Method. We need a differentiable surrogate.

The Logarithmic Smoothing

The Surrogate

We approximate $I_-(u)$ using the function:

$$\hat{I}_-(u) = -(1/t) \log(-u), \quad \text{dom } \hat{I}_- = -\mathbf{R}_{++}$$

Here, $t > 0$ is a parameter that dictates the accuracy of our approximation. The larger $t$ becomes, the more the barrier looks like the true indicator function.

Interiority Constraint

Unlike active-set methods, this approach requires that every iterate $x$ remains strictly feasible ($f_i(x) < 0$). Because the logarithm is undefined for non-negative values, it creates an "impenetrable" barrier that keeps the search inside the interior of the feasible set.

🎯 Definition: Interior-point methods

Interior-point methods: methods for solving convex optimization problems that include inequality constraints by applying Newton's method to a sequence of equality constrained problems.

QUESTION 1

Why can't we use the ideal indicator function $I_-(u)$ directly with Newton's Method?

It is non-differentiable at the boundary u=0.

It makes the objective function non-convex.

It requires the domain to be restricted to positive values.

Newton's method only works for unconstrained problems.

QUESTION 2

What is the effect of increasing the parameter $t$ in the logarithmic barrier approximation?

It makes the approximation smoother and flatter.

It 'sharpen' the transition at the boundary, making it more like the ideal indicator.

It allows the optimization to cross into the infeasible region.

It reduces the problem to a linear programming instance.

QUESTION 3

Which of the following is a mandatory requirement for points $x$ in an interior-point method using log-barriers?

$f_i(x) \ge 0$

$f_i(x) < 0$ for all i

$f_i(x) = 0$ for at least one active constraint

The gradient $\nabla f_0(x)$ must be zero

QUESTION 4

In the trading algorithm analogy, how does the log-barrier behave as risk approaches the limit?

It applies an exponentially increasing penalty to the objective.

It ignores the risk until the limit is actually breached.

It decreases the penalty to encourage finding the boundary.

It shuts down the system immediately.

QUESTION 5

What is the suboptimality gap for a point on the central path with $m$ constraints and parameter $t$?

$t/m$

$m/t$

$\log(m/t)$

$1/t^2$